package leetcode.code1145;

import java.util.Arrays;

import leetcode.helper.tree.TreeNode;

public class Solution {

	int total;
	int x, L, R;

	public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
		total = 0;
		L = 0;
		R = 0;
		this.x = x;
		this.f(root, 0);
		int[] sum = new int[] { L, R, total - L - R - 1 };
		Arrays.sort(sum);
		return sum[2] > sum[0] + sum[1];
	}

	private void f(TreeNode root, int type) {
		if (root == null) {
			return;
		}
		total++;
		boolean b = root.val == x;
		if (type == -1) {
			L++;
		}
		if (type == 1) {
			R++;
		}
		this.f(root.left, b ? -1 : type);
		this.f(root.right, b ? 1 : type);
	}
}
